<html>
<head>
  <title>Math</title>
  <basefont face="微软雅黑" size="2" />
  <meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
  <meta name="exporter-version" content="Evernote Windows/307027 (zh-CN, DDL); Windows/6.1.0 (Win32);"/>
  <style>
    body, td {
      font-family: 微软雅黑;
      font-size: 10pt;
    }
  </style>
</head>
<body>
<a name="1077"/>
<h1>Math</h1>

<div>
<span><div><h2><font style="font-size: 16pt; color: rgb(28, 51, 135);">Modulus - 求模运算</font></h2><div><span style="-en-paragraph: true;">有时计算结果可能会溢出，此时往往需要对结果取余。如果有</span><span style="-en-paragraph: true;">a % m = c % m</span> <span style="-en-paragraph: true;">和</span> <span style="-en-paragraph: true;">b % m = d % m</span><span style="-en-paragraph: true;">, 那么有以下模运算成立。</span></div><ul><li>(a + b) % m = (c + d) % m</li><li>(a - b) % m = (c - d) % m</li><li>(a × b) % m = (c × d) % m</li></ul><div><span style="-en-paragraph: true;">需要注意的是没有除法运算，另外由于最终结果可能溢出，故需要使用更大范围的类型来保存求模之前的结果。另外若</span><span style="-en-paragraph: true;">a</span><span style="-en-paragraph: true;">是负数时往往需要改写为</span> <span style="-en-paragraph: true;">a % m + m</span><span style="-en-paragraph: true;">, 这样就保证结果在</span><span style="-en-paragraph: true;">[0, m - 1]</span><span style="-en-paragraph: true;">范围内了。</span></div><div><br/></div><div><br/></div><div><br/></div><h2>Fast Power - 快速幂运算</h2><div><span style="-en-paragraph: true;">快速幂运算的核心思想为反复平方法，将幂指数表示为2的幂次的和，等价于二进制进行移位计算（不断取幂的最低位），比如</span> <span style="-en-paragraph: true;">x^{22} = x^{16} x^4 x^2</span><span style="-en-paragraph: true;">.</span></div><h3>Java</h3><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902); background-position: initial initial; background-repeat: initial initial;-en-codeblock:true;"><div>import java.util.*;</div><div><br/></div><div>public class FastPow {</div><div>    public static long fastModPow(long x, long n, long mod) {</div><div>        long res = 1;</div><div>        while (n &gt; 0) {</div><div>            // if lowest bit is 1</div><div>            if ((n &amp; 1) != 0) res = res * x % mod;</div><div>            x = x * x % mod;</div><div>            n &gt;&gt;= 1;</div><div>        }</div><div>        return res;</div><div>    }</div><div><br/></div><div>    public static void main(String[] args) {</div><div>        if (args.length != 2 &amp;&amp; args.length != 3) return;</div><div><br/></div><div>        long x = Long.parseLong(args[0]);</div><div>        long n = Long.parseLong(args[1]);</div><div>        long mod = Long.MAX_VALUE;</div><div>        if (args.length == 3) {</div><div>            mod = Long.parseLong(args[2]);</div><div>        }</div><div>        System.out.println(fastModPow(x, n, mod));</div><div>    }</div><div>}</div></div><div><br/></div><div><br/></div><h2>最大公约数(GCD, Greatest Common Divisor)</h2><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">常用的方法为辗转相除法，也称为欧几里得算法。不妨设函数</span><span style="-en-paragraph: true;">gcd(a, b)</span><span style="-en-paragraph: true;">是自然是</span><span style="-en-paragraph: true;">a</span><span style="-en-paragraph: true;">,</span> <span style="-en-paragraph: true;">b</span><span style="-en-paragraph: true;">的最大公约数，不妨设</span><span style="-en-paragraph: true;">a &gt; b</span><span style="-en-paragraph: true;">, 则有</span> <span style="-en-paragraph: true;">a=b×p+qa = b \times p + q</span><span style="-en-paragraph: true;">a</span><span style="-en-paragraph: true;">=</span><span style="-en-paragraph: true;">b</span><span style="-en-paragraph: true;">×</span><span style="-en-paragraph: true;">p</span><span style="-en-paragraph: true;">+</span><span style="-en-paragraph: true;">q</span><span style="-en-paragraph: true;">, 那么对于</span><span style="-en-paragraph: true;">gcd(b, q)</span><span style="-en-paragraph: true;">则是</span><span style="-en-paragraph: true;">b</span><span style="-en-paragraph: true;">和</span><span style="-en-paragraph: true;">q</span><span style="-en-paragraph: true;">的最大公约数，也就是说</span><span style="-en-paragraph: true;">gcd(b, q)</span><span style="-en-paragraph: true;">既能整除</span><span style="-en-paragraph: true;">b</span><span style="-en-paragraph: true;">, 又能整除</span><span style="-en-paragraph: true;">a</span><span style="-en-paragraph: true;">(因为</span> <span style="-en-paragraph: true;">a=b×p+qa = b \times p + q</span><span style="-en-paragraph: true;">a</span><span style="-en-paragraph: true;">=</span><span style="-en-paragraph: true;">b</span><span style="-en-paragraph: true;">×</span><span style="-en-paragraph: true;">p</span><span style="-en-paragraph: true;">+</span><span style="-en-paragraph: true;">q</span><span style="-en-paragraph: true;">,</span> <span style="-en-paragraph: true;">p</span><span style="-en-paragraph: true;">是整数)，如此反复最后得到</span><span style="-en-paragraph: true;">gcd(a, b) = gcd(c, 0)</span><span style="-en-paragraph: true;">, 第二个数为0时直接返回</span><span style="-en-paragraph: true;">c</span><span style="-en-paragraph: true;">. 如果最开始</span><span style="-en-paragraph: true;">a &lt; b</span><span style="-en-paragraph: true;">, 那么</span><span style="-en-paragraph: true;">gcd(b, a % b) = gcd(b, a) = gcd(a, b % a)</span><span style="-en-paragraph: true;">.</span></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">关于时间复杂度的证明：可以分</span><span style="-en-paragraph: true;">a &gt; b/2</span><span style="-en-paragraph: true;">和</span><span style="-en-paragraph: true;">a &lt; b/2</span><span style="-en-paragraph: true;">证明，对数级别的时间复杂度，过程略。</span></div><div><span style="-en-paragraph: true;">与最大公约数相关的还有最小公倍数(LCM, Lowest Common Multiple), 它们两者之间的关系为</span> <span style="-en-paragraph: true;">lcm(a,b)×gcd(a,b)=∣ab∣lcm(a, b) \times gcd(a, b) = |ab|</span><span style="-en-paragraph: true;">l</span><span style="-en-paragraph: true;">c</span><span style="-en-paragraph: true;">m</span><span style="-en-paragraph: true;">(</span><span style="-en-paragraph: true;">a</span><span style="-en-paragraph: true;">,</span><span style="-en-paragraph: true;">b</span><span style="-en-paragraph: true;">)</span><span style="-en-paragraph: true;">×</span><span style="-en-paragraph: true;">g</span><span style="-en-paragraph: true;">c</span><span style="-en-paragraph: true;">d</span><span style="-en-paragraph: true;">(</span><span style="-en-paragraph: true;">a</span><span style="-en-paragraph: true;">,</span><span style="-en-paragraph: true;">b</span><span style="-en-paragraph: true;">)</span><span style="-en-paragraph: true;">=</span><span style="-en-paragraph: true;">∣</span><span style="-en-paragraph: true;">a</span><span style="-en-paragraph: true;">b</span><span style="-en-paragraph: true;">∣</span><span style="-en-paragraph: true;">.</span></div><div><span style="-en-paragraph: true;"><br/></span></div><div><span style="-en-paragraph: true;"><br/></span></div><h1><font style="font-size: 16pt; color: rgb(28, 51, 135);">Prime</font></h1><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">素数：恰好有两个约数的整数，一个是1，另一个则是它自己，比如整数3和5就是素数。素数的基本算法有</span><span style="-en-paragraph: true; font-weight: bold;">素性测试、埃氏筛法和整数分解。</span></div><h2>素性测试</h2><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">如果</span><span style="-en-paragraph: true;">d</span><span style="-en-paragraph: true;">是</span><span style="-en-paragraph: true;">n</span><span style="-en-paragraph: true;">的约数，则易知</span> <span style="-en-paragraph: true;">n=d⋅ndn = d \cdot \frac{n}{d}</span><span style="-en-paragraph: true;">n</span><span style="-en-paragraph: true;">=</span><span style="-en-paragraph: true;">d</span><span style="-en-paragraph: true;">⋅</span><span style="-en-paragraph: true; top: 0.345em;">d</span><span style="-en-paragraph: true; top: -0.394em;">n</span><span style="-en-paragraph: true;">, 因此</span> <span style="-en-paragraph: true;">n/d</span><span style="-en-paragraph: true;">也是</span><span style="-en-paragraph: true;">n</span><span style="-en-paragraph: true;">的约数，且这两个约数中的较小者</span> <span style="-en-paragraph: true;">min(d,n/d)&lt;=n\min(d, n/d) &lt;= \sqrt{n}</span><span style="-en-paragraph: true;">min</span><span style="-en-paragraph: true;">(</span><span style="-en-paragraph: true;">d</span><span style="-en-paragraph: true;">,</span><span style="-en-paragraph: true;">n</span><span style="-en-paragraph: true;">/</span><span style="-en-paragraph: true;">d</span><span style="-en-paragraph: true;">)</span><span style="-en-paragraph: true;">&lt;</span><span style="-en-paragraph: true;">=</span><span style="-en-paragraph: true; top: 0.03971999999999998em;">√</span><span style="-en-paragraph: true; top: 0em;">n</span><span style="-en-paragraph: true;">. 因此我们只需要对前</span> <span style="-en-paragraph: true;">n\sqrt{n}</span><span style="-en-paragraph: true; top: 0.03971999999999998em;">√</span><span style="-en-paragraph: true; top: 0em;">n</span> <span style="-en-paragraph: true;">个数进行处理。</span></div><h2>埃氏筛法</h2><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">素性测试针对的是单个整数，如果需要枚举整数</span><span style="-en-paragraph: true;">n</span><span style="-en-paragraph: true;">以内的素数就需要埃氏筛法了。核心思想是枚举从小到大的素数并将素数的整数倍依次从原整数数组中删除，余下的即为全部素数。</span></div><h2>区间筛法</h2><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">求区间</span><span style="-en-paragraph: true;">[a, b)</span><span style="-en-paragraph: true;">内有多少素数？</span></div><div><span style="-en-paragraph: true;">埃氏筛法得到的是</span><span style="-en-paragraph: true;">[1, n)</span><span style="-en-paragraph: true;">内的素数，求区间素数时不太容易直接求解，我们采取以退为进的思路先用埃氏筛法求得</span><span style="-en-paragraph: true;">[1, b)</span><span style="-en-paragraph: true;">内的素数，然后截取为</span><span style="-en-paragraph: true;">[a, b)</span><span style="-en-paragraph: true;">即可。</span></div><div><span style="-en-paragraph: true;"><br/></span></div><div><span style="-en-paragraph: true;"><br/></span></div><div><span style="-en-paragraph: true;"><br/></span></div><h1><font color="#1C3387">Knapsack - 背包问题</font></h1><div><span style="-en-paragraph: true;">在一次抢珠宝店的过程中，抢劫犯只能抢走以下三种珠宝，其重量和价值如下表所述。</span></div><table><colgroup><col></col><col></col><col></col></colgroup><tbody><tr><td><div>Item(jewellery)<span>    <span>    </span></span></div></td><td><div>Weight<span>    </span></div></td><td><div>Value</div></td></tr><tr><td><div>1</div></td><td><div>6<span>   <span>    <span>    </span></span> <span>    <span>    <span>    </span></span></span></span></div></td><td><div>23</div></td></tr><tr><td><div>2</div></td><td><div>3</div></td><td><div>13</div></td></tr><tr><td><div>3</div></td><td><div>4</div></td><td><div>11</div></td></tr></tbody></table><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">抢劫犯这次过来光顾珠宝店只带了一个最多只能承重17 kg的粉红色小包，于是问题来了，怎样搭配这些不同重量不同价值的珠宝才能不虚此行呢？哎，这年头抢劫也不容易啊...</span></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">用数学语言来描述这个问题就是：</span></div><div><span style="-en-paragraph: true;">背包最多只能承重</span> <span style="-en-paragraph: true;">WW</span><span style="-en-paragraph: true;">W</span> <span style="-en-paragraph: true;">kg, 有</span> <span style="-en-paragraph: true;">nn</span><span style="-en-paragraph: true;">n</span> <span style="-en-paragraph: true;">种珠宝可供选择，这</span> <span style="-en-paragraph: true;">nn</span><span style="-en-paragraph: true;">n</span> <span style="-en-paragraph: true;">种珠宝的重量分别为</span> <span style="-en-paragraph: true;">ω1,⋯,ωn\omega_1,\cdots,\omega_n</span><span style="-en-paragraph: true;">ω</span><span style="-en-paragraph: true; top: 0.15em;">1</span><span style="-en-paragraph: true;">,</span><span style="-en-paragraph: true;">⋯</span><span style="-en-paragraph: true;">,</span><span style="-en-paragraph: true;">ω</span><span style="-en-paragraph: true; top: 0.15em;">n</span><span style="-en-paragraph: true;">, 相应的价值为</span> <span style="-en-paragraph: true;">v1,⋯,vnv_1,\cdots,v_n</span><span style="-en-paragraph: true;">v</span><span style="-en-paragraph: true; top: 0.15em;">1</span><span style="-en-paragraph: true;">,</span><span style="-en-paragraph: true;">⋯</span><span style="-en-paragraph: true;">,</span><span style="-en-paragraph: true;">v</span><span style="-en-paragraph: true; top: 0.15em;">n</span><span style="-en-paragraph: true;">. 问如何选择这些珠宝使得放进包里的珠宝价值最大化？</span></div><div><span style="-en-paragraph: true;"><br/></span></div><h2>Knapsack with repetition - 物品重复可用的背包问题</h2><div><img src="Math_files/Image.png" type="image/png" data-filename="Image.png"/></div><div><img src="Math_files/Image [1].png" type="image/png" data-filename="Image.png"/></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><img src="Math_files/Image [2].png" type="image/png" data-filename="Image.png"/><br/></div><h2>Knapsack without repetition - 01背包问题</h2><div><img src="Math_files/Image [3].png" type="image/png" data-filename="Image.png"/></div><div><span style="-en-paragraph: true;"><br/></span></div><div><span style="-en-paragraph: true;"><br/></span></div><div><span style="-en-paragraph: true;"><br/></span></div><h1>Shuffle and Sampling - 随机抽样和洗牌</h1><div><span style="-en-paragraph: true;"><br/></span></div><div><img src="Math_files/Image [4].png" type="image/png" data-filename="Image.png"/></div><div><img src="Math_files/Image [5].png" type="image/png" data-filename="Image.png"/></div><div><img src="Math_files/Image [6].png" type="image/png" data-filename="Image.png"/></div><div><span style="-en-paragraph: true;"><br/></span></div><h2>Random sampling - 随机抽样</h2><div><span style="-en-paragraph: true;">随机抽样也称为水池抽样，Randomly choosing a sample of k items from a list S containing n items. 大意是从大小为 n 的数组中随机选出 m 个整数，要求每个元素被选中的概率相同。</span></div><h3>题解</h3><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">比较简洁的有算法 Algorithm R, 伪代码如下：</span></div><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902); background-position: initial initial; background-repeat: initial initial;-en-codeblock:true;"><div>/*</div><div>  S has items to sample, R will contain the result</div><div>*/</div><div>ReservoirSample(S[1..n], R[1..k])</div><div>  // fill the reservoir array</div><div>  for i = 1 to k</div><div>      R[i] := S[i]</div><div><br/></div><div>  // replace elements with gradually decreasing probability</div><div>  for i = k+1 to n</div><div>    j := random(1, i)   // important: inclusive range</div><div>    if j &lt;= k</div><div>        R[j] := S[i]</div></div><h2>Implementation and Test case</h2><div><span style="-en-paragraph: true; font-weight: bold;">Talk is cheap, show me the code!</span></div><h3><span style="font-weight: bold;">Java</span></h3><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902); background-position: initial initial; background-repeat: initial initial;-en-codeblock:true;"><div><span style="font-weight: bold;">import java.util.*;</span></div><div><span style="font-weight: bold;">import java.util.Random;</span></div><div><br style="font-weight: bold;"/></div><div><span style="font-weight: bold;">public class Probability {</span></div><div><span style="font-weight: bold;">    public static void main(String[] args) {</span></div><div><span style="font-weight: bold;">        int[] cards = new int[10];</span></div><div><span style="font-weight: bold;">        for (int i = 0; i &lt; 10; i++) {</span></div><div><span style="font-weight: bold;">            cards[i] = i;</span></div><div><span style="font-weight: bold;">        }</span></div><div><span style="font-weight: bold;">        // 100000 times test</span></div><div><span style="font-weight: bold;">        final int times = 100000;</span></div><div><span style="font-weight: bold;">        final int m = 5;</span></div><div><span style="font-weight: bold;">        int[][] count = new int[cards.length][cards.length];</span></div><div><span style="font-weight: bold;">        int[][] count2 = new int[cards.length][m];</span></div><div><span style="font-weight: bold;">        for (int i = 0; i &lt; times; i++) {</span></div><div><span style="font-weight: bold;">            shuffleCard(cards);</span></div><div><span style="font-weight: bold;">            shuffleTest(cards, count);</span></div><div><span style="font-weight: bold;">            int[] sample = randomSample(cards, m);</span></div><div><span style="font-weight: bold;">            shuffleTest(sample, count2);</span></div><div><span style="font-weight: bold;">        }</span></div><div><span style="font-weight: bold;">        System.out.println(&quot;Shuffle cards&quot;);</span></div><div><span style="font-weight: bold;">        shufflePrint(count);</span></div><div><span style="font-weight: bold;">        System.out.println();</span></div><div><span style="font-weight: bold;">        System.out.println(&quot;Random sample&quot;);</span></div><div><span style="font-weight: bold;">        shufflePrint(count2);</span></div><div><span style="font-weight: bold;">    }</span></div><div><br style="font-weight: bold;"/></div><div><span style="font-weight: bold;">    /*</span></div><div><span style="font-weight: bold;">     * shuffle cards</span></div><div><span style="font-weight: bold;">     */</span></div><div><span style="font-weight: bold;">    public static void shuffleCard(int[] cards) {</span></div><div><span style="font-weight: bold;">        if (cards == null || cards.length == 0) return;</span></div><div><br style="font-weight: bold;"/></div><div><span style="font-weight: bold;">        Random rand = new Random();</span></div><div><span style="font-weight: bold;">        for (int i = 0; i &lt; cards.length; i++) {</span></div><div><span style="font-weight: bold;">            int k = rand.nextInt(i + 1);</span></div><div><span style="font-weight: bold;">            int temp = cards[i];</span></div><div><span style="font-weight: bold;">            cards[i] = cards[k];</span></div><div><span style="font-weight: bold;">            cards[k] = temp;</span></div><div><span style="font-weight: bold;">        }</span></div><div><span style="font-weight: bold;">    }</span></div><div><br style="font-weight: bold;"/></div><div><span style="font-weight: bold;">    /*</span></div><div><span style="font-weight: bold;">     * random sample</span></div><div><span style="font-weight: bold;">     */</span></div><div><span style="font-weight: bold;">    public static int[] randomSample(int[] nums, int m) {</span></div><div><span style="font-weight: bold;">        if (nums == null || nums.length == 0 || m &lt;= 0) return new int[]{};</span></div><div><br style="font-weight: bold;"/></div><div><span style="font-weight: bold;">        m = Math.min(m, nums.length);</span></div><div><span style="font-weight: bold;">        int[] sample = new int[m];</span></div><div><span style="font-weight: bold;">        for (int i = 0; i &lt; m; i++) {</span></div><div><span style="font-weight: bold;">            sample[i] = nums[i];</span></div><div><span style="font-weight: bold;">        }</span></div><div><br style="font-weight: bold;"/></div><div><span style="font-weight: bold;">        Random random = new Random();</span></div><div><span style="font-weight: bold;">        for (int i = m; i &lt; nums.length; i++) {</span></div><div><span style="font-weight: bold;">            int k = random.nextInt(i + 1);</span></div><div><span style="font-weight: bold;">            if (k &lt; m) {</span></div><div><span style="font-weight: bold;">                sample[k] = nums[i];</span></div><div><span style="font-weight: bold;">            }</span></div><div><span style="font-weight: bold;">        }</span></div><div><br style="font-weight: bold;"/></div><div><span style="font-weight: bold;">        return sample;</span></div><div><span style="font-weight: bold;">    }</span></div><div><br style="font-weight: bold;"/></div><div><span style="font-weight: bold;">    /*</span></div><div><span style="font-weight: bold;">     * nums[i] = j, num j appear in index i ==&gt; count[j][i]</span></div><div><span style="font-weight: bold;">     */</span></div><div><span style="font-weight: bold;">    public static void shuffleTest(int[] nums, int[][] count) {</span></div><div><span style="font-weight: bold;">        if (nums == null || nums.length == 0) return;</span></div><div><br style="font-weight: bold;"/></div><div><span style="font-weight: bold;">        for (int i = 0; i &lt; nums.length; i++) {</span></div><div><span style="font-weight: bold;">            count[nums[i]][i]++;</span></div><div><span style="font-weight: bold;">        }</span></div><div><span style="font-weight: bold;">    }</span></div><div><br style="font-weight: bold;"/></div><div><span style="font-weight: bold;">    /*</span></div><div><span style="font-weight: bold;">     * print shuffle test</span></div><div><span style="font-weight: bold;">     */</span></div><div><span style="font-weight: bold;">    public static void shufflePrint(int[][] count) {</span></div><div><span style="font-weight: bold;">        if (count == null || count.length == 0) return;</span></div><div><br style="font-weight: bold;"/></div><div><span style="font-weight: bold;">        // print index</span></div><div><span style="font-weight: bold;">        System.out.print(&quot;   &quot;);</span></div><div><span style="font-weight: bold;">        for (int i = 0; i &lt; count[0].length; i++) {</span></div><div><span style="font-weight: bold;">            System.out.printf(&quot;%-7d&quot;, i);</span></div><div><span style="font-weight: bold;">        }</span></div><div><span style="font-weight: bold;">        System.out.println();</span></div><div><span style="font-weight: bold;">        // print num appear in index i in total</span></div><div><span style="font-weight: bold;">        for (int i = 0; i &lt; count.length; i++) {</span></div><div><span style="font-weight: bold;">            System.out.print(i + &quot;: &quot;);</span></div><div><span style="font-weight: bold;">            for (int j = 0; j &lt; count[i].length; j++) {</span></div><div><span style="font-weight: bold;">                System.out.printf(&quot;%-7d&quot;, count[i][j]);</span></div><div><span style="font-weight: bold;">            }</span></div><div><span style="font-weight: bold;">            System.out.println();</span></div><div><span style="font-weight: bold;">        }</span></div><div><span style="font-weight: bold;">    }</span></div><div><span style="font-weight: bold;">}</span></div></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true; font-weight: bold;">以十万次试验为例，左侧是元素</span><span style="-en-paragraph: true; font-weight: bold;">i</span><span style="-en-paragraph: true; font-weight: bold;">, 列代表在相应索引位置出现的次数。可以看出分布还是比较随机的。</span></div><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902); background-position: initial initial; background-repeat: initial initial;-en-codeblock:true;"><div><span style="font-weight: bold;">Shuffle cards</span></div><div><span style="font-weight: bold;">   0      1      2      3      4      5      6      7      8      9</span></div><div><span style="font-weight: bold;">0: 10033  9963   10043  9845   9932   10020  9964   10114  10043  10043</span></div><div><span style="font-weight: bold;">1: 9907   9951   9989   10071  10059  9966   10054  10023  10015  9965</span></div><div><span style="font-weight: bold;">2: 10042  10046  9893   10080  10050  9994   10024  9852   10098  9921</span></div><div><span style="font-weight: bold;">3: 10039  10023  10039  10024  9919   10057  10188  9916   9907   9888</span></div><div><span style="font-weight: bold;">4: 9944   9913   10196  10059  9838   10205  9899   9945   9850   10151</span></div><div><span style="font-weight: bold;">5: 10094  9971   10054  9958   10022  9922   10047  9978   9965   9989</span></div><div><span style="font-weight: bold;">6: 9995   10147  9824   10015  10023  9804   10050  10192  9939   10011</span></div><div><span style="font-weight: bold;">7: 9941   10131  9902   9920   10040  10121  10010  9928   9984   10023</span></div><div><span style="font-weight: bold;">8: 10010  9926   9883   10098  10083  10028  9801   9936   10200  10035</span></div><div><span style="font-weight: bold;">9: 9995   9929   10177  9930   10034  9883   9963   10116  9999   9974</span></div><div><br style="font-weight: bold;"/></div><div><span style="font-weight: bold;">Random sample</span></div><div><span style="font-weight: bold;">   0      1      2      3      4</span></div><div><span style="font-weight: bold;">0: 9966   10026  10078  9966   9891</span></div><div><span style="font-weight: bold;">1: 9958   9806   10066  10022  10039</span></div><div><span style="font-weight: bold;">2: 9923   9936   9964   10051  10083</span></div><div><span style="font-weight: bold;">3: 10165  10088  10184  9928   9916</span></div><div><span style="font-weight: bold;">4: 9998   9990   9973   9931   9832</span></div><div><span style="font-weight: bold;">5: 10026  9932   9873   10085  10035</span></div><div><span style="font-weight: bold;">6: 9942   9972   9990   10030  10026</span></div><div><span style="font-weight: bold;">7: 9903   10153  9997   10051  10044</span></div><div><span style="font-weight: bold;">8: 10082  10066  9804   9899   10147</span></div><div><span style="font-weight: bold;">9: 10037  10031  10071  10037  9987</span></div></div><div><br/></div><div><br/></div><h1>Bitmap</h1><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">最开始接触 bitmap 是在《编程珠玑》这本书上，书中所述的方法有点简单粗暴，不过思想倒是挺好——从信息论的角度来解释就是信息压缩了。即将原来32位表示一个 int 变为一位表示一个 int. 从空间的角度来说就是巨大的节省了(1/32)。可能的应用有</span><span style="-en-paragraph: true; font-weight: bold;">大数据排序/查找（非负整数）</span><span style="-en-paragraph: true;">。</span></div><div><span style="-en-paragraph: true;">C++ 中有</span><span style="-en-paragraph: true;">bitset</span><span style="-en-paragraph: true;">容器，其他语言可用类似方法实现。</span></div></div></span>
</div></body></html> 